package com.code.sort;

import java.util.Arrays;

public class QuickSort {
    public static void sort(int[] arr, int left, int right){
        if(left < right){
            int l = left;
            int r = right;
            int k = arr[l];//基准值，取第一个
            while(l < r){
                while(arr[r] > k && l < r){
                    r--;
                }
                if(l < r){
                    arr[l++] = arr[r];
                }
                while(arr[l] < k && l < r){
                    l++;
                }
                if(l < r){
                    arr[r--] = arr[l];
                }
            }
            arr[l] = k;
            System.out.println(l+"----"+r);
            System.out.println(Arrays.toString(arr));
            sort(arr,left,r-1);
            sort(arr,l+1,right);
        }

    }

    public static void main(String[] args) {

        int[] arr = new int[]{7,2,9,15,4,2,10,1,3};
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
